#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

typedef pair<int, int> interval;

vector<interval>  mergeInterval(vector<interval> &lis)
{
    sort(lis.begin(), lis.end());
    int start = lis[0].first;
    int end = lis[0].second;
    vector<interval> ans;

    for (int i = 1; i < lis.size(); i++) {
        if (end < lis[i].first) {
            ans.push_back(make_pair(start, end));
            start = lis[i].first;
            end = lis[i].second;
         } else {
            end = max(end, lis[i].second);
         }
    }
    ans.push_back(make_pair(start, end));
    return ans;
}

vector<interval> insertInterval(vector<interval> lis, const interval &a)
{
    vector<interval> ans;

    lis.push_back(a);
    ans = mergeInterval(lis); 
    return ans;
}


int main(int argc, char **argv)
{
    vector<interval> lis;
    vector<interval> lis1;
    vector<interval> lis2;

    cout << "-----------------Test 1--------------------" << endl;
    lis.clear();
    lis1.clear();
    lis.push_back(make_pair(1,4));
    lis.push_back(make_pair(8,10));
    lis.push_back(make_pair(7,12));
    lis.push_back(make_pair(13,14));
    lis.push_back(make_pair(19,24));
    lis.push_back(make_pair(24,34));
    lis.push_back(make_pair(61,74));
    lis.push_back(make_pair(31,44));
    lis1 = mergeInterval(lis);
    for (int i = 0; i < lis1.size(); i++) {
        cout << lis1[i].first << " " << lis1[i].second << endl;
    }
    cout << endl;
    lis2 = insertInterval(lis1, interval(16,35));
    for (int i = 0; i < lis2.size(); i++) {
        cout << lis2[i].first << " " << lis2[i].second << endl;
    }

    cout << "-----------------Test 2--------------------" << endl;
    lis.clear();
    lis1.clear();
    lis2.clear();
    lis.push_back(make_pair(1,4));
    lis.push_back(make_pair(8,10));
    lis.push_back(make_pair(7,12));
    lis.push_back(make_pair(13,14));
    lis.push_back(make_pair(19,24));
    lis.push_back(make_pair(24,34));
    lis.push_back(make_pair(61,74));
    lis.push_back(make_pair(31,44));
    lis1 = mergeInterval(lis);
    for (int i = 0; i < lis1.size(); i++) {
        cout << lis1[i].first << " " << lis1[i].second << endl;
    }
    cout << endl;
    lis2 = insertInterval(lis1, interval(14,35));
    for (int i = 0; i < lis2.size(); i++) {
        cout << lis2[i].first << " " << lis2[i].second << endl;
    }


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
